package leetcode.tree_problem;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 347. 前 K 个高频元素
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 */
public class 前K个高频元素 {
    private class Pare implements Comparable<Pare> {
        int key;
        int times;

        public Pare(int key, int times) {
            this.key = key;
            this.times = times;
        }

        @Override
        public int compareTo(Pare o) {
            return this.times - o.times;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];//操作数组，存放处理的结果
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums
        ) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);//第一次出现
            }
        }
        Queue<Pare> queue = new PriorityQueue<>();//存放要处理的前k个元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()//遍历map
        ) {
            if (queue.size() < k) {
                queue.offer(new Pare(entry.getKey(), entry.getValue()));
            } else {
                Pare cur = queue.peek();
                if (cur.times > entry.getValue()) {
                    continue;
                } else {
                    queue.poll();
                    queue.offer(new Pare(entry.getKey(), entry.getValue()));
                }
            }

        }
        for (int i = 0; i < ret.length; i++) {
            ret[i] = queue.poll().key;
        }

        return ret;
    }
}
